package Hash;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

//两数之和
public class two_um {
    /*
    * 给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
        你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
        你可以按任意顺序返回答案。
        示例 1：
        输入：nums = [2,7,11,15], target = 9
        输出：[0,1]
        解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
     * */

    /**
     *解题：
     * 1.从数组里面找出两个整数，使得和为target
     * 这里应该是已知数量的，所以是不是可以先利用target-数组的数，然后再看数组里面是否包含即可
     * 要返回的是索引，所以还得知道位置
     */
    public int[] twoSum_1(int[] nums, int target) {
        //key 为数组的值 value为索引
        HashMap<Integer,Integer> map=new HashMap<>();
        //这里先去将num先存储进来
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],i);
        }
        for (int i = 0; i < nums.length; i++) {
            //这里去求得所要的值
            int num=target-nums[i];
            //如果为true 则证明找到了
            //因为不能重复,所以这里利用索引不能一样的原则去判断
            if(map.containsKey(num)&&i!=map.get(num)){
                return new int[]{i, map.get(num)};
            }

        }
        return null;
    }
    //更加快捷的方法
    public int[] twoSum_2(int[] nums, int target) {
        //key 为数组的值 value为索引
        HashMap<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            //这里去求得所要的值
            int num=target-nums[i];
            //如果为true 则证明找到了
            //因为不能重复,所以这里利用索引不能一样的原则去判断
            if(map.containsKey(num)&&i!=map.get(num)){
                return new int[]{i, map.get(num)};
            }
            //todo:如果前面的找不到所要的值，这里先去存储起来即可
            //nums = [2,7,11,15], target = 9
            // 原因：这里是先去得到2，然后map是空的，因为9-2=7，这里的7确实nums有，但是map没有，所以这里是进行下一个循环，但是没有影响
            //          因为这里的9-7=2，是一样的，所以不用担心要找的数还没有存进map导致错误的问题，因为遍历到后面会去找前面的数，结果是一样的
            map.put(nums[i],i);
        }
        return null;
    }
}
